package com.tys.algorithm.advanced.code.class02;

import java.util.HashMap;
import java.util.HashSet;


/**
 * 数组中其他数都出现了M次,只有一种数出现了K次，返回出现K次的这种数
 * 数组中其他数都出现了M次,没有一种数出现K次，返回-1
 * 1 <= K < M
 */
public class Code04_KM {

    //使用数组方法
    public static int onlyKTimes(int[] arr, int k, int m) {
        //每个正数都可以表示为二进制的32位
        int[] help = new int[32];
        for (int num : arr) {
            //判断数的每个位置是否是1，有1则累加
            for (int i = 0; i < 32; i++) {
                help[i] += (num >> i) & 1; //简写
//                if(((num >> i) & 1) != 0){
//                    help[i]++;
//                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            //如果是t[i]是0时
            if (help[i] % m == 0) {
                continue;
            }

            //如果不能整除m，则证明K次的数在该位置有1
            if (help[i] % m == k) {
                ans |= (1 << i); //在i位上有1，或运算到结果中
            } else {
                return -1;
            }
        }

        //如果是help[i]是0时：是否是0出现k次
        if (ans == 0) {
            int count = 0;
            for (int num : arr) {
                if (num == 0) {
                    count++;
                }
            }
            //不是0出现k次则返回-1
            if (count != k) {
                return -1;
            }
        }

        return ans;
    }

    //使用hash表方法
    public static int test(int[] arr, int k, int m) {
        //hash表计数
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }

        //找到K次的数
        for (int num : map.keySet()) {
            if (map.get(num) == k) {
                return num;
            }
        }
        return -1;
    }


    //对数器，随机一个数组 出现k次,m次, k<m, 设置最大种数
    public static int[] randomArray(int maxKinds, int range, int k, int m) {
        int ktimeNum = randomNumber(range); //[-range, range]
        //0.5概览出现k次，其他出现1 到 m-1次
        int ktimes = Math.random() < 0.5 ? k : (int) (Math.random() * (m - 1)) + 1;
        int numKinds = (int) (Math.random() * maxKinds) + 2; //2以上
        int[] arr = new int[ktimes + (numKinds - 1) * m]; //数组长度
        int index = 0;

        //填K次的数
        for (; index < ktimes; index++) {
            arr[index] = ktimeNum;
        }
        numKinds--;

        //填m次的数
        HashSet<Integer> set = new HashSet<>();
        set.add(ktimeNum);
        while (numKinds != 0) {
            //确保生成新的数
            int curNum = 0;
            do {
                curNum = randomNumber(range);
            } while (set.contains(curNum));
            set.add(curNum);
            numKinds--;
            //放m次这个数
            for (int i = 0; i < m; i++) {
                arr[index++] = curNum;
            }
        }

        //打乱
        for (int i = 0; i < arr.length; i++) {
            int j = (int) (Math.random() * arr.length);
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        return arr;
    }

    //生成随机数：[-range,range]
    public static int randomNumber(int range) {
        return ((int) (Math.random() * range) + 1) - ((int) (Math.random() * range) + 1);
    }

    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + ", ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
//        int[]arr = {90, 90, 78, 90, 78, 90, 90, 90, 78};
//        System.out.println(onlyKTimes(arr, 3, 6));

        int[] arr2 = {-1, 3, 1, 3, 3, 1, 1, -1};
        System.out.println(onlyKTimes(arr2, 2, 3));

        System.out.println("================");

        int maxKinds = 100;
        int range = 200;
        int testTime = 100000;
        int max = 9;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int a = (int) (Math.random() * max) + 1;//1-9
            int b = (int) (Math.random() * max) + 1;
            int k = Math.min(a, b);
            int m = Math.max(a, b);
            //k<m
            if (k == m) {
                m++;
            }

            int[] arr = randomArray(maxKinds, range, k, m);
            int ans1 = test(arr, k, m);
            int ans2 = onlyKTimes(arr, k, m);
            if (ans1 != ans2) {
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println("出错了");
                printArray(arr);
                break;
            }
        }
        System.out.println("测试结束");
    }
}
